package ext;

import java.util.Arrays;

import org.junit.Test;

import util.ArrayGenerator;

public class MinAbs {
    
    public int minAbs(int[] nums) {
        int n = nums.length;
        if (n == 1) {
            return nums[0];
        } else if (n == 2) {
            return Math.min(Math.abs(nums[0]), Math.abs(nums[1]));
        } else {
            if (nums[0] >= 0) {
                return nums[0];
            } else if (nums[n - 1] <= 0) {
                return nums[n - 1];
            }
        }
        int lo = 1, hi = n - 2;
        while (lo <= hi) {
            int m = (hi - lo) / 2 + lo;
            if (Math.abs(nums[m - 1]) > Math.abs(nums[m]) && Math.abs(nums[m]) < Math.abs(nums[m + 1])) {
                return nums[m];
            } else if (Math.abs(nums[m - 1]) <= Math.abs(nums[m])) {
                hi = m - 1;
            } else {
                lo = m + 1;
            }
        }
        return 0;
    }

    @Test
    public void test() {
        int[] nums = ArrayGenerator.getArray(-10, 10, 10);
        Arrays.sort(nums);
        nums = new int[]{-5, -5, 2, 2, 3, 3, 4, 5, 5, 9};
        // System.out.println(Arrays.toString(nums));
        for (int i = 0; i < 10; i++) {
            nums[i] = -9 + i;
        }
        System.out.println(minAbs(nums));
    }

}
